//括号生成
class Solution {
public:
    int n;
    string path;
    vector<string> ret;
    void dfs(int left,int right)
    {
        if(left == n && right == n)
        {
            ret.push_back(path);
            return;
        }
        if(left == n)
        {
            path += ')';
            dfs(left,right+1);
            path.pop_back();
        }
        else if(left >= right)
        {
            //必须是左括号个数大于右括号
            path += '(';
            dfs(left+1,right);
            path.pop_back();
            path += ')';
            dfs(left,right+1);
            path.pop_back();
        }
        //left:左括号个数 ， right:右括号个数
        
    }
    vector<string> generateParenthesis(int _n) {
        n = _n;
        dfs(0,0);
        return ret;
    }
};

//最长有效括号
class Solution {
public:
    int longestValidParentheses(string s) {
        //状态表示：以s[i]位置结尾的最长有效子字符串的长度
        int n = s.size();
        if(n < 2) return 0;
        vector<int> dp(n);
        if(s[0] == '(' && s[1] == ')') dp[1] = 2;
        int ret = 0;
        for(int i = 2 ; i < n ; ++i)
        {
            ret = max(ret,dp[i-1]);
            if(s[i] == '(') continue;
            else 
            {
                if(s[i-1] == '(')
                {
                    dp[i] = dp[i-2]+2;
                }
                else 
                {
                    //找到与s[i-1]配对的前一个位置
                    if(i-dp[i-1]-1 < 0 || s[i-dp[i-1]-1] == ')') continue;  
                    dp[i] = dp[i-1]+2;
                    if(i-dp[i-1]-2 < 0) continue;
                    dp[i] += dp[i-dp[i-1]-2];
                }
            }

        }
        ret = max(ret,dp[dp.size()-1]);
        return ret;
    }
};
